//class Solution {
//    public int minCostClimbingStairs(int[] cost) {
//        int n = cost.length; // 总共有n阶台阶[0, n-1]
//        int[] dp = new int[n+1];
//        dp[0] = 0;
//        dp[1] = 0;
//        for (int i = 2; i <= n; i++) {
//            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
//        }
//        return dp[n]; // 到第n阶台阶的最少费用，一定要跳出去
//    }
//}


class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length; // 总共有n阶台阶[0, n-1]
        int[] dp = new int[n];
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for (int i = n-3; i >= 0; i--) {
            dp[i] = Math.min(dp[i+1], dp[i+2]) + cost[i];
        }
        // 返回 从0位置到达楼顶的的费用 与 从1位置到达楼顶的费用 的较小值
        return Math.min(dp[0], dp[1]);
    }
}